package day6;

import java.util.Stack;

public class Main2 {
    /**
     * NC115 栈和排序
     * https://www.nowcoder.com/practice/95cb356556cf430f912e7bdf1bc2ec8f?tpId=196&tqId=37173&ru=/exam/oj
     */
    public int[] solve (int[] a) {
        int n = a.length;
        Stack<Integer> stack = new Stack<>();
        int aim = n; // 每次都是想要出最大值
        boolean[] visit = new boolean[n + 1]; // 记录1~n哪些元素入栈，为了进行出栈

        int[] ret = new int[n];
        int index = 0;
        for(int x : a) {
            stack.push(x);
            visit[x] = true;

            while(visit[aim] == true) {
                // 说明要取出的大值，已经入栈，那么将这个目标值进行减小
                aim--;
            }

            // 出栈
            while(!stack.isEmpty() && stack.peek() >= aim) {
                ret[index++] = stack.peek();
                stack.pop();
            }
        }
        return ret;
    }
}
